/*
 *  Brno University of Technology
 *
 *  Copyright (C) 2009-2010 by Brno University of Technology and the contributors
 *
 *  Complete list of developers available at our web site:
 *
 *       http://spl.utko.feec.vutbr.cz
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see http://www.gnu.org/licenses/.
 */
/**
 * Tree based genetic programming
 */
package cz.vutbr.feec.utko.ef.gp.tree;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.Vector;

import org.apache.log4j.Logger;
import org.graphviz.GraphViz;

import cz.vutbr.feec.utko.ef.core.Random;
import cz.vutbr.feec.utko.ef.evolution.Chromozome;
import cz.vutbr.feec.utko.ef.evolution.DisplayType;
import cz.vutbr.feec.utko.ef.grammar.Grammar;
import cz.vutbr.feec.utko.ef.grammar.Rule;
import cz.vutbr.feec.utko.ef.individuals.Action;
import cz.vutbr.feec.utko.ef.individuals.Constants;
import cz.vutbr.feec.utko.ef.individuals.CrossoverIsNotPossibleException;
import cz.vutbr.feec.utko.ef.individuals.MutationIsNotPossibleException;
import cz.vutbr.feec.utko.ef.individuals.SymbolEnum;
import cz.vutbr.feec.utko.ef.terminals.IntegerTerminal;
import cz.vutbr.feec.utko.ef.visualizer.VisualizerRegister;

/**
 * The Class Chromozome represent an individual in genetic programming. It is
 * the tree of shapes.
 */
public class TreeChromozome extends Chromozome {

	/** The Constant serialVersionUID. */
	private static final long serialVersionUID = 8303272798234449463L;

	/** The grammar. */
	transient private Grammar grammar;

	/** The root. */
	private Node root = null;
	
	private String codeToVisualizer;

	/** The log. */
	transient private static Logger log = Logger
			.getLogger(TreeChromozome.class);

	/** The id counter. */
	private int idCounter = 0;

	/** The max tree height. */
	private int maxTreeHeight;

	/**
	 * Instantiates a new tree chromozome.
	 * 
	 * @param g
	 *            the grammar
	 * @param maxTreeHeight
	 *            the max tree height
	 */
	public TreeChromozome(Grammar g, int maxTreeHeight) {
		this.maxTreeHeight = maxTreeHeight;
		grammar = g;
		// validate
		if (g.getProductionLength("ROOT") > maxTreeHeight
				|| g.getProductionLength("ROOT") == Constants.INFINITE) {
			throw new RuntimeException(
					"Not possible to generate such a chromozome. "
							+ "Minimal production length required for the ROOT "
							+ "token is " + g.getProductionLength("ROOT")
							+ " max., requested tree hieght was "
							+ maxTreeHeight);
		}
		// create root node
		int currentDeep = 0;
		int maxProductionLength = maxTreeHeight - currentDeep;
		Rule rule = grammar.getRandomRule("ROOT", maxProductionLength);
		root = new Node(rule);
		root.setDeep(0);

		generateRestOfTheTree(root);

		// for debug purposes only
		validate();
	}

	/**
	 * Adds the child nodes to the parent node.
	 * 
	 * @param parent
	 *            the parent
	 * @param maxHeight
	 *            the maximal height of node
	 * 
	 * @return the list of nodes
	 */
	private List<Node> addChildNodes(Node parent, int maxHeight) {
		LinkedList<Node> res = new LinkedList<Node>();
		// get random rule, that can be applicable to parent
		for (int index = 0; index < parent.getChildren().length; index++) {
			Rule childRule = grammar.getRandomRule(parent.getRule()
					.getChildTokens()[index], maxHeight - parent.getDeep());
			// create new node
			Node newChild = new Node(parent, index, childRule);

			// connect links between nodes
			parent.setChild(newChild, index);
			res.addFirst(newChild);

			String dest = "";
			for (String n : childRule.getChildTokens()) {
				dest += n;
			}
			log.debug("Adding node " + parent + " -> " + newChild);

			modifyHeightOfParents(newChild);
			modifyWeightsOfParents(newChild, 1);
		}
		return res;
	}

	/**
	 * Creates deep copy of the chromozome.
	 * 
	 * @return the new cloned chromozome
	 * 
	 * @throws CloneNotSupportedException
	 */
	public TreeChromozome cloneDeep() {
		try {
			// clone chromozome
			TreeChromozome newChromozome;
			newChromozome = (TreeChromozome) this.clone();
			// clone root node
			if (root == null) {
				// it contains zero nodes ?
				return newChromozome;
			} else {
				newChromozome.root = this.root.cloneDeep(null);
			}
			assert newChromozome.root != this.root;
			// tree traversing and the rest of nodes cloning
			LinkedList<Node> stackOriginal = new LinkedList<Node>();
			stackOriginal.add(root);

			LinkedList<Node> stackCopy = new LinkedList<Node>();
			stackCopy.add(newChromozome.root);

			while (!stackOriginal.isEmpty()) {
				// remove first
				Node nodeOrig = stackOriginal.pollFirst();
				Node nodeCopy = stackCopy.pollFirst();

				// add nodeOrig successors to stackOriginal
				for (int i = nodeOrig.getChildren().length - 1; i >= 0; i--) {
					// original
					stackOriginal.addFirst(nodeOrig.getChildren()[i]);

					// copy
					Node clonedNode = nodeOrig.getChildren()[i]
							.cloneDeep(nodeCopy);
					assert clonedNode != nodeOrig.getChildren()[i];
					nodeCopy.getChildren()[i] = clonedNode;
					assert nodeCopy.getChildren()[i] != nodeOrig.getChildren()[i];
					stackCopy.addFirst(nodeCopy.getChildren()[i]);
				}

				// make copy
			}
			assert stackCopy.isEmpty();
			return newChromozome;
		} catch (CloneNotSupportedException e) {
			e.printStackTrace();
		}
		return null;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Comparable#compareTo(java.lang.Object)
	 */
	@Override
	public int compareTo(Chromozome o) {
		assert o.getCachedFitness() != null;
		assert getCachedFitness() != null;
		return new Double(this.getCachedFitness()).compareTo(o
				.getCachedFitness());
	}

	/**
	 * Crossover operator.
	 * 
	 * @param ch
	 *            chromozome - second parent for a crossover
	 * 
	 * @return the chromozome
	 * 
	 * @throws CrossoverIsNotPossibleException
	 *             the crossover is not possible exception
	 * 
	 */
	public void crossover(Chromozome ch)
			throws CrossoverIsNotPossibleException {

		// 01) Get a set of non-terminal nodes, except root and make a new set
		// NT (NT is a set of Ns)
		// N = (Z, coord), where Z is a non-terminal node, coord are coordinates
		// of Node

		// Crossover non-terminal or all symbols
		Set<Node> nodeSet = this.getSetOfSymbols(SymbolEnum.ALL_SYMBOLS);
		// Set<Node> NT = getSetOfNonterminals();

		// remove root
		nodeSet.remove(root);

		for (;;) {

			// 02) Select a crossover node (CN1)
			if (nodeSet.isEmpty()) {
				// crossover would be worthless, only root can be crossed
				throw new CrossoverIsNotPossibleException();
			}

			// Set is not empty, select element of this set at random
			Node CN1 = this.removeRandomNode(nodeSet);

			// 03) Getting information of CN1's parent
			// code is removed and replaced

			// 04) Calculate the 3-tuple T = (length, position, productionRule)
			// Crossover node rule length
			int CN1Length = CN1.getParent().getChildren().length;
			// Crossover node position
			int CN1Position = CN1.getParentIndex();

			// Set of rules, which can be used for generating successors
			Vector<Rule> R = getAllPossibleRules(CN1, CN1Length);

			// And Remove elements, where children on position != CN1Position
			// are not corresponding in crossover node production rule
			assert CN1Length >= 0;
			assert CN1Position >= 0;
			removePositionNotMatchingRules(R, CN1, CN1Length, CN1Position);

			// 07) Make a set X, where are only non-terminals on MNPosition
			Vector<String> X = selectMatchingSymbols(R, CN1Position);

			for (;;) {

				// 08) If X != 0, then one of elements (CS) is randomly picked
				// up and a set PN = [symbol, coord] is counted
				// from second parent else we have to remove CS from set NT and
				// continue with point 2

				if (X.isEmpty()) {
					// CN1 is already removed from NT
					break;
				}

				String CS = selectRandomSymbol(X);

				Vector<Node> PN;

				if (CN1.isTerminal()) {
					PN = getNodesFromSecondParent((TreeChromozome)ch, CS, SymbolEnum.TERMINALS);
				} else {
					PN = getNodesFromSecondParent((TreeChromozome)ch, CS,
							SymbolEnum.NON_TERMINALS);
				}

				for (;;) {

					// 09) If PN != 0, we have to pick up CN2 from PN by random
					// else we have to remove CS from X and go back to point 8

					if (PN.isEmpty()) {

						for (int i = 0; i < X.size(); i++) {
							if (X.get(i).toString().equals(CS)) {
								X.remove(i);
								i--;
							}
						}

						break;
					}

					// Get Random Node from PN set and remove it
					Node CN2 = this.removeRandomNode(new HashSet<Node>(PN));
					PN.remove(CN2);

					// 10) Evaluation of P1 and P2. Is possible to switch trees?

					int P1 = CN1.getDeep() + CN2.getHeight();
					int P2 = CN1.getHeight() + CN2.getDeep();

					if (P1 <= maxTreeHeight && P2 <= maxTreeHeight) {

						// 11) Crossover operation (switching CN1 and CN2)

						log.debug("*************************** Crossover: ");
						log.debug(CN1.nodeId + ", hash = " + CN1.hashCode());
						log.debug(CN2.nodeId + ", hash = " + CN2.hashCode());

						log.info("CROSSOVERED");

						// Swap nodes
						swapNodes(CN1, CN2);

						// reset both chromozome fitnesses
						this.resetCachedFitness();
						ch.resetCachedFitness();

						return;

					} else {
						// CN2 is already removed
						continue;
					}
				}
			}
		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	@Override
	public boolean equals(Object obj) {
		if (!(obj instanceof TreeChromozome)) {
			return false;
		}
		TreeChromozome ch = (TreeChromozome) obj;
		return getCachedFitness() == ch.getCachedFitness();
	}

	/**
	 * Exist rule with production length.
	 * 
	 * @param node
	 *            the node
	 * @param cS
	 *            the symbol
	 * 
	 * @return true, if successful
	 */
	private boolean existRuleWithProductionLength(Node node, String cS) {
		int ML = maxTreeHeight - node.getDeep();
		return (grammar.getProductionLength(cS) <= ML);
	}

	/**
	 * Generate code which can be used independently on the evolutionary
	 * framework and also can be used to compound results of evolution to a new
	 * filter.
	 * 
	 * @return the JAVA code of component
	 */
	public String generateCode() {
		String s = generateCode(root);
		return s;
	}
	

	public String getCodeToVisualizer() {
		return codeToVisualizer;
	}

	/**
	 * Generate code.
	 * 
	 * @param node
	 *            the node
	 * 
	 * @return the string
	 */
	private String generateCode(Node node) {
		assert node.getAction() != null;
/*
		node.nodeId = idCounter++;
		if (node.isTerminal()) {
			// initiate new terminal
			String className = node.getAction().getClass().getSimpleName();

			return  className + " n" + node.nodeId + " = new " + className + "();\n";
		} else {
			// initiate new nonterminal action
			String className = node.getAction().getClass().getSimpleName();
			String s = className + " n" + node.nodeId + " = new " + className
					+ "();\n";

			// call action over the operator
			for (int i = 0; i < node.getChildren().length; i++) {
				s += generateCode(node.getChildren()[i]);
			}
			String ids = "";
			for (int i = 0; i < node.getChildren().length; i++) {
				ids += "n" + node.getChildren()[i].nodeId + ", ";
			}
			ids = ids.substring(0, ids.length() - 2);
			s += "// " + node.getRule() + node.getAction().getSymbol() + "\n";
			s += "n" + node.nodeId + ".getResult(" + ids + ");\n";

			return s;
		}
		*/
		
		
		// Upravil radek u integer terminalu chcu vypsat konkretni int cislo
		
		assert node.getAction() != null;

		node.nodeId = idCounter++;
		if (node.isTerminal()) {
			// initiate new terminal
			String className = node.getAction().getClass().getSimpleName();

			
			String s = className + " n" + node.nodeId + " = new " + className + "();\n";
			if (node.getAction().getClass() == IntegerTerminal.class)
				s += "n" + node.nodeId + ".setValue(" + node.getAction().getSymbol() + ");\n";

			String out = "Object i" + node.nodeId;
			s += out + " = n" + node.nodeId + ".getValue();\n";
			
			return s;			
		} else {
			String out = "Object i" + node.nodeId;
			// initiate new nonterminal action
			String className = node.getAction().getClass().getSimpleName();
			String s = className + " n" + node.nodeId + " = new " + className
					+ "();\n";

			// call action over the operator
			for (int i = 0; i < node.getChildren().length; i++) {
				s += generateCode(node.getChildren()[i]);
			}
			String ids = "";
			for (int i = 0; i < node.getChildren().length; i++) {
				ids += "(Object)i" + node.getChildren()[i].nodeId + ", ";
			}
			ids = ids.substring(0, ids.length() - 2);
			s += "// " + node.getRule() + node.getAction().getSymbol() + "\n";
			s += out + " = n" + node.nodeId + ".getValue(" + ids + ");\n";

			return s;
		}		
		
	}

	/**
	 * @param root
	 *            the root node of the subtree
	 */
	private void generateRestOfTheTree(Node root) {
		// generate the rest of nodes
		LinkedList<Node> stack = new LinkedList<Node>();
		stack.add(root);
		while (!stack.isEmpty()) {
			Node n = stack.poll();
			for (Node node : addChildNodes(n, maxTreeHeight)) {
				stack.addFirst(node);
			}
		}
	}

	/**
	 * Gets the all possible rules.
	 * 
	 * @param node
	 *            the node
	 * @param lengthOfRule
	 *            the length of rule
	 * 
	 * @return the all possible rules
	 */
	private Vector<Rule> getAllPossibleRules(Node node, int lengthOfRule) {

		// Get all possible rules terminal-node can be crossovered with
		Vector<Rule> R = new Vector<Rule>(Arrays.asList(grammar
				.getSuccessor(node.getParent().getNonterminalName())));

		// 05) Remove every operation from R, where length of consequent !=
		// lengthOfRule

		for (int i = 0; i < R.size(); i++) {
			if (R.get(i).getChildTokens().length != lengthOfRule) {
				R.remove(i);
				i--;
			}
		}

		// 06) Remove every different action from R
		for (int i = 0; i < R.size(); i++) {
			if (!R.get(i).getAction().getSymbol().equals(
					node.getParent().getAction().getSymbol())) {
				R.remove(i);
				i--;
			}
		}

		log.debug("************************************");
		if (log.isDebugEnabled()) {
			for (Rule rule : R) {
				log.debug(rule + " action: " + rule.getAction().getSymbol());
			}
		}

		return R;
	}

	/**
	 * Gets the max tree height.
	 * 
	 * @return the max tree height
	 */
	public int getMaxTreeHeight() {
		return maxTreeHeight;
	}

	/**
	 * Gets the node description.
	 * 
	 * @param n
	 *            the node
	 * @param name
	 *            the name
	 * @param imagePath
	 *            the image path
	 * @param displayType
	 *            the display type
	 * 
	 * @return the node description
	 */
	private String getNodeDescription(Node n, String name, String imagePath,
			DisplayType displayType, Integer id) {
		String param;
		String idMarker;
		if (id == null) {
			idMarker = "";
		} else {
			idMarker = id.toString() + "_";
		}

		if (imagePath == null) {
			if (!n.isTerminal()) {
				param = "shape=ellipse";
			} else if (n.isInputParameter()) {
				param = "shape=\"doubleoctagon\",style=filled,"
						+ "color=grey,fontcolor=black";
			} else {
				// regular parameter
				param = "shape=\"doubleoctagon\"";
			}
		} else {
			param = "image=\"" + imagePath + "\"";
		}
		if (DisplayType.WITH_HASHCODE.equals(displayType)) {
			return "[" + param + ",label=\"" + name + ", id = " + n.hashCode()
					+ "\" ] \n";
		} else if (DisplayType.WITH_IMAGES.equals(displayType)) {
			// save this node image
			VisualizerRegister.visualize("vizualize/tmp/" + idMarker
					+ n.hashCode() + ".gif", n);
			return "[shape=box,label=\""
					+ name
					+ "\" color=blue, fontcolor=red,labelloc=\"b\" ,URL=\"vizualize/tmp/"
					+ idMarker + n.hashCode() + ".gif\",image=\"vizualize/tmp/"
					+ idMarker + n.hashCode() + ".gif\" ] \n";
		} else if (DisplayType.DETAIL.equals(displayType)) {
			String sh = "";
			for (int i = 0; i < n.getChildren().length; i++) {
				sh += n.getSubTreeHeight(i) + ",";
			}
			return "[" + param + ",label=\"" + name + ", id = " + n.hashCode()
					+ "\\n D:" + n.getDeep() + " W:" + n.getWeight() + ",H:"
					+ n.getHeight() + "(" + sh + ") INDEX:"
					+ n.getParentIndex() + " \" ] \n";
		} else {
			return "[" + param + ",label=\"" + name + "\" ] \n";
		}
	}

	/**
	 * Gets the node id which will be used for generating GraphViz scheme.
	 * 
	 * @param n
	 *            the node
	 * 
	 * @return the node id
	 */
	private String getNodeId(Node n) {
		if (n.isInputParameter()) {
			return "" + n.getAction().hashCode();
		} else {
			return "" + n.hashCode();
		}
	}

	/**
	 * Gets the nodes from second parent which are possible for crossover.
	 * 
	 * @param ch
	 *            the second chromozome to crossover
	 * @param cs
	 *            the symbol which is crossed
	 * @param terminals
	 * @return
	 * 
	 * @return the nodes from second parent
	 */
	private Vector<Node> getNodesFromSecondParent(TreeChromozome ch, String cs,
			SymbolEnum terminals) {

		Vector<Node> PN = new Vector<Node>(ch.getSetOfSymbols(terminals));

		for (int i = 0; i < PN.size(); i++) {
			if (!PN.get(i).getNonterminalName().equals(cs)) {
				PN.remove(i);
				i--;
			}
		}

		log.debug("************************************");
		if (log.isDebugEnabled()) {
			for (Node node : PN) {
				log.debug(node.getNonterminalName() + ", ");
			}
		}

		return PN;
	}

	/**
	 * Gets the number of program input parameters.
	 * 
	 * @return the number of program input parameters
	 */
	public int getNumberOfProgramInputParameters() {
		return grammar.getNumberOfProgramInputParameters();
	}

	/**
	 * Gets the possible rules.
	 * 
	 * @param cS
	 *            the symbol
	 * 
	 * @return the possible rules
	 */
	private Vector<Rule> getPossibleRules(String cS) {
		Vector<Rule> result = new Vector<Rule>(Arrays.asList(grammar
				.getSuccessor(cS)));

		log.debug("************************************");
		if (log.isDebugEnabled()) {
			for (Rule rule : result) {
				log.debug(rule + " action: " + rule.getAction().getSymbol());
			}
		}

		return result;
	}

	/**
	 * Gets the program input parameter.
	 * 
	 * @param index the index
	 * 
	 * @return the program input parameter
	 */
	public Action getProgramInputParameter(int index) {
		return grammar.getProgramInputParameters(index);
	}

	/**
	 * Gets the result.
	 * 
	 * @return the result
	 */
	@Override
	public Object getResult() {
		return this.root.getResult();
	}

	/**
	 * Gets the root.
	 * 
	 * @return the root
	 */
	public Node getRoot() {
		return this.root;
	}

	/**
	 * Gets the set the of all symbols which are equals to typeOfSymbol.
	 * 
	 * @param typeOfSymbol
	 *            the type of symbol
	 * 
	 * @return the set the of all symbols
	 */
	private Set<Node> getSetOfSymbols(SymbolEnum typeOfSymbol) {

		Set<Node> result = new HashSet<Node>();

		LinkedList<Node> stack = new LinkedList<Node>();

		// Deep-first tree passing
		stack.add(root);
		while (!stack.isEmpty()) {
			// remove first
			Node n = stack.poll();
			for (int i = n.getChildren().length - 1; i >= 0; i--) {
				stack.addFirst(n.getChildren()[i]);
			}
			switch (typeOfSymbol) {
			case TERMINALS:
				if (n.isTerminal()) {
					result.add(n);
				}
				break;
			case NON_TERMINALS:
				if (!n.isTerminal()) {
					result.add(n);
				}
				break;
			case ALL_SYMBOLS:
				result.add(n);
				break;
			}
		}
		return result;
	}

	/**
	 * Modify height of parents.
	 * 
	 * @param node
	 *            the node
	 */
	private void modifyHeightOfParents(Node node) {
		Node tmp = node;
		while (tmp.getParent() != null) {
			int height = tmp.getHeight();
			int index = tmp.getParentIndex();
			tmp.getParent().setSubTreeHeight(index, height);

			tmp = tmp.getParent();
		}
	}

	/**
	 * Modify weights of parents.
	 * 
	 * @param node
	 *            the node
	 * @param value
	 *            the value
	 */
	private void modifyWeightsOfParents(Node node, int value) {
		Node tmp = node.getParent();
		while (tmp != null) {
			tmp.setWeight(tmp.getWeight() + value);
			tmp = tmp.getParent();
		}
	}

	/**
	 * Mutate the chromozome at a random node.
	 * 
	 * @return true, if successfully mutated
	 * 
	 * @throws MutationIsNotPossibleException
	 * 
	 */
	public void mutate() throws MutationIsNotPossibleException {
		this.validate();

		// 01) Get a set of non-terminal nodes, except root and make a new set
		// NT (NT is a set of Ns)
		// N = (Z, coord), where Z is a non-terminal node, coord are coordinates
		// of Node

		Set<Node> NT = this.getSetOfSymbols(SymbolEnum.ALL_SYMBOLS);

		// Remove root
		NT.remove(root);

		for (;;) {

			// 02) Select a mutation node (CN1)
			if (NT.isEmpty()) {
				// Mutation is not possible...
				throw new MutationIsNotPossibleException();
			}

			// Set is not empty, select element of this set at random
			Node MN = this.removeRandomNode(NT);
			// 03) Getting information of MN's parent
			// code is removed and replaced

			// 04) Calculate the 3-tuple T = (length, position, productionRule)
			// Mutation node rule length
			int MNLength = MN.getParent().getChildren().length;
			// Mutation node position
			int MNPosition = MN.getParentIndex();

			// Set of rules, which can be used for generating successors
			Vector<Rule> R = getAllPossibleRules(MN, MNLength);

			// And Remove elements, where children on position != MNPosition
			// are not corresponding to mutation nod production rule
			removePositionNotMatchingRules(R, MN, MNLength, MNPosition);

			// 07) Make a set X, where are only non-terminals on MNPosition
			Vector<String> X = selectMatchingSymbols(R, MNPosition);

			for (;;) {
				// 08) If X != 0, then one of elements (CS) is randomly picked
				// up and a set PN = [symbol, coord] is counted
				// from second parent else we have to remove CS from set NT and
				// continue with point 2

				if (X.isEmpty()) {
					// MN is already removed from NT
					break;
				}

				String CS = selectRandomSymbol(X);

				// 11) Set PP of production rules of CS
				Vector<Rule> PP = getPossibleRules(CS);

				if (PP.isEmpty()) {
					// Is not possible to find a mutation to generate valid
					// individual with a depth less than D
					X.remove(CS);
					continue;
				}

				if (MN.isTerminal()) {
					// All rules with different production length are removed
					// (production length is 1)
					for (int i = 0; i < PP.size(); i++) {
						if (PP.get(i).getProductionLength() != MN.getRule()
								.getProductionLength()) {
							PP.remove(i);
							i--;
						}
					}
				}

				if (!existRuleWithProductionLength(MN, CS)) {
					// Production length is out of bounds
					X.remove(CS);
					continue;
				}

				// 12) Get random production rule from PP
				Rule rule = selectRandomRule(PP);

				log.debug("Random rule = " + rule);
				log.debug(this);

				replaceWithRandomSubtree(MN, rule);
				return;
			}
		}
	}

	/**
	 * Removes the position not matching rules.
	 * 
	 * @param R
	 *            the set of possible rules
	 * @param node
	 *            the node
	 * @param ruleLength
	 *            the rule length
	 * @param nodePosition
	 *            the node position
	 */
	private void removePositionNotMatchingRules(Vector<Rule> R, Node node,
			int ruleLength, int nodePosition) {
		for (int i = 0; i < R.size(); i++) {
			for (int j = 0; j < ruleLength; j++) {
				if (nodePosition != j) {
					// FIXME RADIM
					if (!node.getParent().getChildren()[j].getNonterminalName()
							.equals(R.get(i).getChildTokens()[j])) {
						R.remove(i);
						i--;
						if (i < 0) {
							return;
						}

					}
				}
			}
		}
	}

	/**
	 * Removes the random node.
	 * 
	 * @param s
	 *            the set of Nodes
	 * 
	 * @return random node of the chromozome tree.
	 */
	private Node removeRandomNode(Set<Node> s) {
		Random rnd = new Random();
		Node n = (Node) s.toArray()[rnd.nextInt(s.size())];
		s.remove(n);
		return n;
	}

	/**
	 * Replace text.
	 * 
	 * @param from the from
	 * @param to the to
	 */
	private void replaceText(String from, String to) {
		String str;
		try {
			BufferedReader input = new BufferedReader(new FileReader(from));
			BufferedWriter output = new BufferedWriter(new FileWriter(to));

			while (null != ((str = input.readLine()))) {
				String result = str.replaceAll("vizualize/tmp", "../tmp");
				output.write(result);
			}
			input.close();
			output.close();
		} catch (IOException ioe) {
			System.err.println("I/O Error - " + ioe);
		}

	}

	/**
	 * Replace with random subtree.
	 * 
	 * @param currentSubtree
	 *            the mutation node
	 * @param rule
	 *            the production rule of new node
	 */
	private void replaceWithRandomSubtree(Node currentSubtree, Rule rule) {
		int oldHeight = currentSubtree.getWeight();
		Node newSubtree = new Node(currentSubtree.getParent(), currentSubtree
				.getParentIndex(), rule);
		int weightDiff = newSubtree.getWeight() - oldHeight;

		// odecti od Weight zmenu ve vaze
		modifyWeightsOfParents(currentSubtree, weightDiff);
		modifyHeightOfParents(newSubtree);

		assert newSubtree.getDeep() == currentSubtree.getDeep() : "toMutation has deep: "
				+ newSubtree.getDeep()
				+ " but should have deep"
				+ currentSubtree.getDeep();

		generateRestOfTheTree(newSubtree);

		if (log.isDebugEnabled()) {
			this.visualize(newSubtree, "Mutation.png", DisplayType.BRIEF, null);
		}

		// 13) If terminal symbol is mutated, continue and mutate non-terminal
		// symbol

		// Mutate only nonterminal symbols
		// if (toMutation.isTerminal()) {
		// continue;
		// }

		currentSubtree.getParent().setChild(newSubtree,
				currentSubtree.getParentIndex());

		log.info("MUTATED");
		log.debug("-------------------------- toMutation hash = "
				+ newSubtree.hashCode());
		log.debug(this);

		resetCachedFitness();
	}

	/**
	 * Select matching symbols.
	 * 
	 * @param r
	 *            the set of all possible rules
	 * @param mNPosition
	 *            the mutation node position
	 * 
	 * @return the vector of matching symbols
	 */
	private Vector<String> selectMatchingSymbols(Vector<Rule> r, int mNPosition) {
		Vector<String> X = new Vector<String>();
		for (Rule rule : r) {
			if (mNPosition <= rule.getChildTokens().length && mNPosition > 0) {
				X.add(rule.getChildTokens()[mNPosition]);
			} else {
				continue;
			}
		}

		log.debug("************************************");
		if (log.isDebugEnabled()) {
			for (String string : X) {
				log.debug(string);
			}
		}

		return X;
	}

	/**
	 * Select random rule from the set provided.
	 * 
	 * @param setOfProductionRulesP
	 *            the set of production rules
	 * 
	 * @return the randomly selected rule
	 */
	private Rule selectRandomRule(Vector<Rule> setOfProductionRulesP) {
		return (Rule) setOfProductionRulesP.get((new Random())
				.nextInt(setOfProductionRulesP.size()));
	}

	/**
	 * Select random symbol.
	 * 
	 * @param x
	 *            the set of possible symbols
	 * 
	 * @return the randomly selected symbol
	 */
	private String selectRandomSymbol(Vector<String> x) {
		return x.get((new Random()).nextInt(x.size()));
	}

	/**
	 * Swap two nodes in the tree.
	 * 
	 * @param n1
	 *            the c n1
	 * @param n2
	 *            the c n2
	 */
	private void swapNodes(Node n1, Node n2) {

		// System.err.println("Swap N1:" + n1.hashCode() + " N2:" +
		// n2.hashCode());
		// System.err.println("Swap N1Parent:" + n1.getParent().hashCode()
		// + " N2Parent:" + n2.getParent().hashCode());

		int n1ParentIndex = n1.getParentIndex();
		int n2ParentIndex = n2.getParentIndex();

		int n1Weight = n1.getWeight();
		int n2Weight = n2.getWeight();

		Node n1Parent = n1.getParent();
		Node n2Parent = n2.getParent();

		n1.setParent(n2Parent);
		n2Parent.setChild(n1, n2ParentIndex);
		n1.setParentIndex(n2ParentIndex);

		n2.setParent(n1Parent);
		n1Parent.setChild(n2, n1ParentIndex);
		n2.setParentIndex(n1ParentIndex);

		updateDeepOfChildren(n1);
		updateDeepOfChildren(n2);

		modifyWeightsOfParents(n1, n1Weight - n2Weight);
		modifyWeightsOfParents(n2, n2Weight - n1Weight);

		modifyHeightOfParents(n1);
		modifyHeightOfParents(n2);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		String s = "";
		LinkedList<Node> stack = new LinkedList<Node>();
		stack.add(root);
		while (!stack.isEmpty()) {
			Node n = stack.poll();
			for (int i = 0; i < n.getDeep(); i++) {
				s += " ";
			}
			s += " +-" + n + "\n";
			for (int i = n.getChildren().length - 1; i >= 0; i--) {
				stack.addFirst(n.getChildren()[i]);
			}
		}
		return s;
	}

	/**
	 * Update deep of children.
	 * 
	 * @param node the node
	 */
	private void updateDeepOfChildren(Node node) {
		LinkedList<Node> stack = new LinkedList<Node>();
		stack.add(node);
		while (!stack.isEmpty()) {
			Node tmp = stack.poll();
			for (Node n : tmp.getChildren()) {
				stack.addLast(n);
			}
			tmp.setDeep(tmp.getParent().getDeep() + 1);
		}
	}

	/* (non-Javadoc)
	 * @see cz.vutbr.feec.utko.ef.evolution.Chromozome#validate()
	 */
	public void validate() {
		if (root.getDeep() != 0) {
			throw new RuntimeException("Root has not deep 0");
		}
		if (root.getParent() != null) {
			throw new RuntimeException("Root has parent ");
		}

		// kontrola deep
		LinkedList<Node> queue = new LinkedList<Node>();
		queue.addFirst(root);
		while (!queue.isEmpty()) {
			Node n = queue.getLast();
			queue.removeLast();
			for (Node node : n.getChildren()) {
				queue.addFirst(node);
			}
			if (n != root && n.getDeep() != n.getParent().getDeep() + 1) {
				visualize("debug.png", DisplayType.DETAIL);
				System.err.println("Chromozome visualized to 'debug.png'");
				throw new RuntimeException("The node (" + n.hashCode()
						+ ") has wrong deep: " + n.getDeep() + " should be: "
						+ (n.getParent().getDeep() + 1));
			}
			if (n.isTerminal() && n.getDeep() == 0) {
				throw new RuntimeException(
						"Terminal is at root position and may not be.");
			}
			for (int i = 0; i < n.getChildren().length; i++) {
				if (n.getChildren()[i].getParentIndex() != i) {
					visualize("debug.png", DisplayType.DETAIL);
					System.err.println("Chromozome visualized to 'debug.png'");
					throw new RuntimeException("Node (" + n.hashCode()
							+ ") has incorect parent index: "
							+ n.getChildren()[i].getParentIndex()
							+ ", should be " + i);
				}
				// Zkontroluj, jestli potomek ukazuje na predka
				if (n != n.getChildren()[i].getParent()) {
					visualize("debug.png", DisplayType.DETAIL);
					System.err.println("Chromozome visualized to 'debug.png'");
					throw new RuntimeException("Node (" + n.hashCode()
							+ ") has incorect parent-child linking: Parent:"
							+ n.hashCode() + ", Child: "
							+ n.getChildren()[i].hashCode() + " but it is "
							+ n.getChildren()[i].getParent().hashCode());
				}
			}
		}

		// Kontrola weight
		LinkedList<Node> stack = new LinkedList<Node>();
		stack.addFirst(root);
		while (!stack.isEmpty()) {
			Node n = stack.getLast();
			stack.removeLast();
			for (Node node : n.getChildren()) {
				stack.addLast(node);
			}
			LinkedList<Node> innerStack = new LinkedList<Node>();
			innerStack.add(n);
			int counter = 0;
			while (!innerStack.isEmpty()) {
				Node n2 = innerStack.getLast();
				innerStack.removeLast();
				for (Node node : n2.getChildren()) {
					innerStack.addLast(node);
				}
				counter++;
			}
			if (counter != n.getWeight()) {
				visualize("debug.png", DisplayType.DETAIL);
				System.err.println("Chromozome visualized to 'debug.png'");
				throw new RuntimeException("Weight (" + n.hashCode() + ") is "
						+ n.getWeight() + " but should be " + counter
						+ " TERMINAL:" + n.isTerminal());
			}
		}

		// check height at terminals
		LinkedList<Node> stack3 = new LinkedList<Node>();
		stack3.addFirst(root);
		while (!stack3.isEmpty()) {
			Node n = stack3.getLast();
			stack3.removeLast();
			for (Node node : n.getChildren()) {
				stack3.addLast(node);
			}
			if (n.isTerminal() && n.getHeight() != 1) {
				throw new RuntimeException(
						"Terminal has different height than 1 :"
								+ n.getHeight());
			}
		}
		// check grammar
		validateGrammar();

		LinkedList<Node> stack4 = new LinkedList<Node>();
		stack4.addFirst(root);
		while (!stack4.isEmpty()) {
			Node n = stack4.getLast();
			stack4.removeLast();
			for (Node node : n.getChildren()) {
				stack4.addLast(node);
			}
			if (n.isTerminal() && n.getHeight() != 1) {
				visualize("debug.png", DisplayType.DETAIL);
				System.err.println("Chromozome visualized to 'debug.png'");
				throw new RuntimeException("Terminal (" + n.hashCode()
						+ ") have height " + n.getHeight()
						+ " but should have 1.");
			}
			if (!n.isTerminal() && n.getHeight() <= 0) {
				visualize("debug.png", DisplayType.DETAIL);
				System.err.println("Chromozome visualized to 'debug.png'");
				throw new RuntimeException("Nonterminal (" + n.hashCode()
						+ ") have height " + n.getHeight()
						+ " but should have greater or equal 1.");
			}
			if (n != root) {
				int h = n.getParent().getSubTreeHeight(n.getParentIndex());
				if (h != n.getHeight()) {
					visualize("debug.png", DisplayType.DETAIL);
					System.err.println("Chromozome visualized to 'debug.png'");
					throw new RuntimeException("Wrong height detected ("
							+ n.hashCode() + ")- parent reports: " + h
							+ " but current node reports " + n.getHeight());

				}
			}
		}
	}

	/**
	 * Validate grammar.
	 */
	private void validateGrammar() {
		LinkedList<Node> stack3 = new LinkedList<Node>();
		stack3.addFirst(root);
		while (!stack3.isEmpty()) {
			Node n = stack3.getLast();
			stack3.removeLast();
			for (Node node : n.getChildren()) {
				stack3.addLast(node);
			}
			// zkontroluj nasledniky
			if (!n.isTerminal()) {
				Rule[] possibleRules = grammar.getSuccessor(n.getRule()
						.getFromToken());
				// for each possible rule
				boolean res = false;
				for (int j = 0; j < possibleRules.length; j++) {
					// check rule successor
					res = res || validateRule(n, possibleRules[j]);
				}
				// zadny neodpovidal
				if (!res) {
					String skutecnost = n.getNonterminalName() + " -> ";
					for (Node node : n.getChildren()) {
						skutecnost += node.getNonterminalName() + ",";
					}

					String moznosti = "";
					for (Rule rule : possibleRules) {
						moznosti += rule + "\n";
					}

					throw new RuntimeException("The node (" + n.hashCode()
							+ ") has invalid successors. It has structure: \n"
							+ skutecnost
							+ "\n\nBut allowed alternatives are: \n\n"
							+ moznosti);
				}
			}
		}
	}

	/**
	 * odpovidaji potomci uzlu n pravidlu rule ?
	 * 
	 * @param n
	 *            node
	 * @param rule
	 *            pravidlo
	 * @return pravdu, pokud je vse ok
	 */
	private boolean validateRule(Node n, Rule rule) {
		if (n.getChildren().length != rule.getChildTokens().length) {
			return false;
		}
		for (int i = 0; i < rule.getChildTokens().length; i++) {
			if (!rule.getChildTokens()[i].equals(n.getChildren()[i]
					.getNonterminalName())) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Visualize.
	 * 
	 * @param node
	 *            the node
	 * @param filename
	 *            the filename
	 */
	public void visualize(Node node, String filename, DisplayType displayType,
			Integer id) {

		String s = "";
		LinkedList<Node> stack = new LinkedList<Node>();
		stack.add(node);
		while (!stack.isEmpty()) {
			Node n = stack.poll();
			if (n.getParent() == null) {
				s += getNodeId(n)
						+ getNodeDescription(n, "ROOT", null, displayType, id);
			} else {
				s += getNodeId(n)
						+ getNodeDescription(n, n.getAction().getSymbol(), n
								.getAction().getSymbolImage(), displayType, id);
			}
			for (int i = 0; i < n.getChildren().length; i++) {
				stack.addFirst(n.getChildren()[i]);
				if (displayType.equals(DisplayType.DETAIL)) {
					s += getNodeId(n) + " ->" + getNodeId(n.getChildren()[i])
							+ "[ label=\""
							+ n.getChildren()[i].getParentIndex()
							+ "\" arrowtail=\"none\" arrowhead=\"none\"];"
							+ "\n";
				} else {
					s += getNodeId(n) + " ->" + getNodeId(n.getChildren()[i])
							+ "[ arrowtail=\"none\" arrowhead=\"none\"];"
							+ "\n";
				}
			}
		}
		s += "FITNESS[label=\"FITNESS:" + getCachedFitness() + "\"]";

		GraphViz gv = new GraphViz();
		gv.addln(gv.start_graph());
		// gv.addln("size=\"2,7\";");
		gv.add(s);
		gv.addln(gv.end_graph());
		
		this.codeToVisualizer = s;

		File out = new File(filename + ".tmp");
		gv.writeGraphToFile(gv.getGraph(gv.getDotSource()), out);
		replaceText(filename + ".tmp", filename);
		out.delete();
	}

	/**
	 * @see visualize(String filename, DisplayType type)
	 * 
	 * @param filename
	 *            the filename
	 */
	public void visualize(String filename) {
		this.visualize(this.root, filename, DisplayType.BRIEF, null);
	}

	/**
	 * Generate graph image into file. Supported file types are txt, png, jpg,
	 * gif, svg, fig, svgz, ps, ps2, gd and gd2. An example is depicted in the
	 * figure below. The root of the program has a single successor - the
	 * operator PLUS. This operator has two other children. In the tree there
	 * are distinguished two basic blocks - terminals (has no any successors)
	 * and non-terminals (has at least one successor). The order of input params
	 * in the resulting image is accommodated to be easily displayed. The true
	 * order of the parameters is given by the index of an edge. I.e. the edge
	 * with index 0 is first and with index 1 is second. This mean that the
	 * operator minus in the following figure stands for (8-4) and not for
	 * (4-8)\image html images/minus.png.
	 * 
	 * 
	 * There are also a special kind of terminals, which are an inputs of an
	 * program depicted as an filled gray circles. The order of the program
	 * params are in the pre-order way, i.e. "8" is first, 5 is second and 7 is
	 * the last program input. All the rest of program terminals are internal
	 * program constants.
	 * 
	 * \image html images/LogicalTree.png
	 * 
	 * @param filename
	 *            the filename to be written the image in the GIF format
	 */
	public void visualize(String filename, DisplayType type) {
		visualize(filename, type, null);
	}

	/**
	 * Visualize.
	 * 
	 * @param filename the filename
	 * @param type the type
	 * @param id the id
	 */
	public void visualize(String filename, DisplayType type, Integer id) {
		this.visualize(this.root, filename, type, id);
	}
}
